package com.qrpcw.algorithms;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;

public class BucketSort {

	public static void main(String[] args) {
		double[] data = new double[]{0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.68};
		BucketSort test = new BucketSort();
		data = test.concatenate(test.bucketSort(data));
		System.out.println(Arrays.toString(data));
	}
	
	public ArrayList<ArrayList<Double>> bucketSort(double[] A){
		int n = A.length;
		ArrayList<ArrayList<Double>> B = new ArrayList<ArrayList<Double>>(n);
		for(int i=0; i<n; i++){
			B.add(i,new ArrayList<Double>());
		} // let B[0~n-1] be a new array
		for(int i =0; i<n; i++){   
            int t = (int)Math.floor(n*A[i]);
            B.get(t).add(A[i]); 
        } //insert A[i] to B[floor(n*A[i])]
		for(int i=0; i<=n-1;i++){
			insertionSort(B.get(i));
		} //sort each Bucket B[i] with Insertion Sort
		return B;
	}
	
	//concatenate the lists B[1],B[2] ~ B[n-1] together in order
	public double[] concatenate(ArrayList<ArrayList<Double>> b){
		double[] result = new double[b.size()];
		int counter = 0;
		Iterator<ArrayList<Double>> it = b.iterator();
		while(it.hasNext()){
			Iterator<Double> n = it.next().iterator();
			while(n.hasNext()){
				result[counter] = n.next();
				counter++;
			}
		}
		return result;
	}
	
	public ArrayList<Double> insertionSort(ArrayList<Double> a){
		int i,j;
		double key;
		for(i=1;i<a.size();i++){
			j = i-1;
			key = a.get(i);
			while(j>=0 && a.get(j)>key){
				a.set(j+1, a.get(j));
				j = j-1;
				a.set(j+1, key);
			}
		}
		return a;
	}
}